/*
 * shell_sort.cpp
 *
 *  Created on: May 4, 2014
 *      Author: Lhmily
 */

#include "../header/base.h"
#include "../header/compare.h"

template<typename Elem, typename Comp>
void insert_sort_for_shell(Elem A[], int n, int incr) {
	for (int i = incr; i < n; i += incr)
		for (int j = i; (j >= incr) && (Comp::prior(A[j], A[j - incr])); j -=
				incr)
			swap(A, j, j - incr);
}

template<typename Elem, typename Comp>
void shell_sort(Elem A[], int n) {
	for (int i = n / 2; i > 2; i /= 2)
		for (int j = 0; j < i; ++j)
			insert_sort_for_shell<Elem, Comp>(&A[j], n - j, i);
	insert_sort_for_shell<Elem, Comp>(A, n, 1);
}

template<typename E, typename Comp>
void sort(E* array, int n) {
	shell_sort<E, Comp>(array, n);
}

#include "../test.cpp"

int main(int argc, char **argv) {

	return testMain<minintCompare>(argc, argv); //
}

